package com.kevinkk.graph;

import java.util.List;
import java.util.ArrayList;

/**
 * 给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
 *  graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。
 *
 *
 *  【邻接矩阵】+【回溯】
 */

public class AllPathsFromSourceToTarget {
    class Solution {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();

        public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
            path.add(0);    // 从 0 节点开始遍历（起点是固定的）
            backtracking(graph, 0);
            return res;
        }

        // n 表示当前遍历到的节点
        private void backtracking(int[][] graph, int n){
            if(n == graph.length-1){    // 当到达 n-1 节点时，一个路径就遍历完了
                res.add(new ArrayList<>(path));
                return;
            }

            for(int i = 0; i < graph[n].length; i++){
                path.add(graph[n][i]);
                backtracking(graph, graph[n][i]);   // 继续遍历下一个节点
                path.remove(path.size()-1);
            }
        }
    }

}
